/* 
 * Copyright (c) 2012 JSquirrelEngine
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in 
 * the Software without restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the
 * Software, and to permit persons to whom the Software is furnished to do so, subject
 * to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
 * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 * 
 */

package org.jsquirrel.geometry;

import org.jsquirrel.math.F2Vector;
import org.jsquirrel.math.FInterval;
import org.jsquirrel.math.Transform2D;



/**
 * Abstract class for Polygon. This class implements different geometric operations such as
 * intersection checking and transform, regardless the inner data structure used for storing
 * the vertices.
 * 
 * @author Juan David Adarve Bermudez
 *
 */
public abstract class Polygon {

	//*********************************************************************************************
	// INSTANCE ATTRIBUTES
	//*********************************************************************************************
	
	/**
	 * Bounding area used
	 */
	protected BoundingArea boundingArea;
	
	/**
	 * Flag for indicating the use of bounding area on this polygon
	 */
	protected boolean useBoundingArea;
	
	
	//*********************************************************************************************
	// CONSTRUCTOR
	//*********************************************************************************************
	
	/**
	 * Default constructor, set the use of bounding area as false 
	 */
	public Polygon() {
		
		useBoundingArea = false;
		boundingArea = null;
	}
	
	
	//*********************************************************************************************
	// FINAL METHODS
	//*********************************************************************************************
	
	/**
	 * 
	 */
	public final void addVertex(F2Vector vertex) {
		
		addVertexImpl(vertex);
		
		if(useBoundingArea) {
			boundingArea.update(this);		
		}
	}
	
	public final void addVertex(float x, float y) {
				
		addVertexImpl(x, y);
		
		if(useBoundingArea) {
			boundingArea.update(this);
		}		
	}
	
	public final void useBoundingArea(BoundingArea area) {
		
		useBoundingArea = area == null? false : true;
		if(useBoundingArea) {
			
			// just to be sure that the previous bounding box is to be deleted...
			boundingArea = null;
			
			boundingArea = area;
			if(length() > 0) {
				
				boundingArea = area;
				boundingArea.update(this);
			}
			
		}
		else {
			boundingArea = null;
		}
		
	}
	
	
	public final BoundingArea getBoundingArea() {
		return boundingArea;
	}
	
	
	
	@Override
	public final String toString() {
		
		StringBuffer buffer = new StringBuffer();
		
		buffer.append("v={");
		VertexIterator iterator = getIterator();
		while(iterator.hasNext()) {
			F2Vector tuple = iterator.next();
			buffer.append("(" + tuple.x + ", " + tuple.y + ") ");
		}
		
		// removes the last space inserted when printing all the vertices
		buffer.deleteCharAt(buffer.length() - 1);
		buffer.append("}");
		
		// bounding box
		if(useBoundingArea) {
			buffer.append(boundingArea);
		}
		
		return buffer.toString();
	}

	
	public final boolean intersects(Polygon p) {
		
		// if both polygons are using the bounding boxes
		if(this.useBoundingArea && p.useBoundingArea) {			
			
			try {
				if(this.boundingArea.intersects(p.boundingArea)) {
					return computeIntersection(p);
				}
				else {
					return false;
				}
				
			} catch(UnsupportedBoundingIntersectionException e) {
				System.err.print(e);				
				return computeIntersection(p);
			}
		}
		// in case one or both polygons do not use bounding box
		else {
			return computeIntersection(p);			
		}
	}
	
	public final boolean intersectsRectangle(float xLeft, float yLeft, float width, float height) {
		
		if(this.useBoundingArea) {
			
			try{
				if(this.boundingArea.intersectsRectangle(xLeft, yLeft, width, height)) {
					
					return computeRectangleIntersection(xLeft, yLeft, width, height);
				} else {
					return false;
				}
				
			}
			// in case the operation is not supported by the BoundingArea implementation...
			catch(UnsupportedBoundingIntersectionException e) {
					return computeRectangleIntersection(xLeft, yLeft, width, height);
			}			
		}
		
		return computeRectangleIntersection(xLeft, yLeft, width, height);
	}
	
	public final void getBoundingRectangle(F2Vector bLeftCorner, F2Vector uRightCorner) {
		
		if(this.useBoundingArea) {
			
			this.boundingArea.getBoundingRectangle(bLeftCorner, uRightCorner);
			return;
		}
		
		FInterval projection = new FInterval();
		
		// vertical projection
		F2Vector axis = new F2Vector(0, 1);
		this.projectIntoVector(axis, projection);
		
		bLeftCorner.setY(projection.lowerBound());
		uRightCorner.setY(projection.upperBound());
		
		
		// horizontal projection
		axis.setX(1);
		axis.setY(0);
		this.projectIntoVector(axis, projection);
		
		bLeftCorner.setX(projection.lowerBound());
		uRightCorner.setX(projection.upperBound());		
	}
	
	
	public final void transform(Transform2D t) {
		
		VertexIterator iterator = getIterator();
		
		while(iterator.hasNext()) {
			
			F2Vector vertex = iterator.next();
			t.transform(vertex);
		}
		
		// updating of the bounding area
		if(useBoundingArea) {
			boundingArea.update(this);
		}
	}
	
	
	/**
	 * Performs the transformation of this polygon and stores the result on
	 * the Polygon p. It is assumed by this method that both this and the
	 * Polygon parameter have the same number of vertex.
	 * 
	 * @param t  transform to apply
	 * @param p  Polygon where the result is to be stored
	 */
	public final void transform(Transform2D t, Polygon p) {
		
		VertexIterator it = getIterator();
		VertexIterator itP = p.getIterator();
		
		while(it.hasNext() && itP.hasNext()) {
			
			F2Vector v = it.next();
			F2Vector vP = itP.next();
			
			t.transform(v, vP);
		}
		
		// if the P parameter has bounding area, it has to be updated with the new vertex
		if(p.boundingArea != null) {
			p.boundingArea.update(p);
		}
	}
	
	
	
	
	//*********************************
	// ABSTRACT METHODS
	//*********************************
	
	/**
	 * Add a new vertex to the polygon copying the value from
	 * the parameter
	 * 
	 * @param vertex: the new vertex to insert
	 */
	protected abstract void addVertexImpl(F2Vector vertex);
	
	protected abstract void addVertexImpl(float x, float y);
	
	/**
	 * 
	 * @return returns the number of vertices in the polygon
	 */
	public abstract int length();
	
	/**
	 * 
	 * @return returns a new iterator to scan the vertices of the polygon
	 */
	public abstract VertexIterator getIterator();
	
	
	
	//*********************************
	// PROTECTED METHODS
	//*********************************
	
	protected boolean intersectsImpl(Polygon p) {
		
		VertexIterator iterator = getIterator();
		
		F2Vector axis = new F2Vector();
		F2Vector firstVertex = (F2Vector)iterator.next();
		F2Vector prevVertex = firstVertex;
		
		FInterval projectionThis = new FInterval();
		FInterval projectionP = new FInterval();
		
		while(iterator.hasNext()) {
			F2Vector vertex = (F2Vector)iterator.next();
			
			// computes the axis for this edge
			F2Vector.sub(vertex, prevVertex, axis);
			axis.normalize();
			F2Vector.perpendicularVector(axis, axis);

			// Projections of the polygons in the axis
			this.projectIntoVector(axis, projectionThis);
			p.projectIntoVector(axis, projectionP);
			
			if(!projectionThis.intersects(projectionP)) {
				return false;
			}
			
			prevVertex = vertex;
		}
		
		// projection on the axis formed by the last and first vertices
		F2Vector.sub(prevVertex, firstVertex, axis);
		axis.normalize();
		F2Vector.perpendicularVector(axis, axis);
		
		this.projectIntoVector(axis, projectionThis);
		p.projectIntoVector(axis, projectionP);
		
		if(!projectionThis.intersects(projectionP)) {
			return false;
		}
		
		return true;
	}
	
	protected void projectIntoVector(F2Vector axis, FInterval interval) {
		
		VertexIterator iterator = getIterator();
		
		F2Vector vertex = (F2Vector)iterator.next();		
		float b1 = vertex.dotProduct(axis);
		
		vertex = (F2Vector)iterator.next();
		float b2 = vertex.dotProduct(axis);
		
		interval.setBounds(b1, b2);
		
		while(iterator.hasNext()) {
			float v = axis.dotProduct((F2Vector)iterator.next());
			interval.updateToFit(v);
		}
	}
	
	//*********************************
	// PRIVATE METHODS
	//*********************************
	
	private final boolean computeIntersection(Polygon p) {
		
		boolean a = this.intersectsImpl(p);
		
		// if the intersection between this polygon and the parameter is true, one must check the p against this
		if(a) {
			return p.intersectsImpl(this);
		}
		
		return false;
	}
	
	private final boolean computeRectangleIntersection(float xLeft, float yLeft, float width, float height) {
		
		VertexIterator iterator = getIterator();
		
		F2Vector axis = new F2Vector();
		F2Vector firstVertex = (F2Vector)iterator.next();
		F2Vector prevVertex = firstVertex;
		
		FInterval projectionThis = new FInterval();
		FInterval projectionR = new FInterval();
		
		while(iterator.hasNext()) {
			F2Vector vertex = (F2Vector)iterator.next();
			
			// computes the axis for this edge
			F2Vector.sub(vertex, prevVertex, axis);
			axis.normalize();
			F2Vector.perpendicularVector(axis, axis);

			// Projections of the polygons in the axis
			this.projectIntoVector(axis, projectionThis);
			projectRectangleIntoVector(xLeft, yLeft, width, height, axis, projectionR);
			
			if(!projectionThis.intersects(projectionR)) {
				return false;
			}
			
			prevVertex = vertex;
		}
		
		// projection on the axis formed by the last and first vertices
		F2Vector.sub(prevVertex, firstVertex, axis);
		axis.normalize();
		F2Vector.perpendicularVector(axis, axis);
		
		this.projectIntoVector(axis, projectionThis);
		projectRectangleIntoVector(xLeft, yLeft, width, height, axis, projectionR);
		
		if(!projectionThis.intersects(projectionR)) {
			return false;
		}
		
		//*************************************************
		// projection of this polygon on the rectangle axis
		//*************************************************
		
		// vector perpendicular to X axis
		axis.x = 0;
		axis.y = 1;
		this.projectIntoVector(axis, projectionThis);
		projectRectangleIntoVector(xLeft, yLeft, width, height, axis, projectionR);
		if(!projectionThis.intersects(projectionR)) {
			return false;
		}
		
		// vector perpendicular to Y axis
		axis.x = 1;
		axis.y = 0;
		this.projectIntoVector(axis, projectionThis);
		projectRectangleIntoVector(xLeft, yLeft, width, height, axis, projectionR);
		if(!projectionThis.intersects(projectionR)) {
			return false;
		}
		
		return true;
	}
	
	private void projectRectangleIntoVector(float xLeft, float yLeft, float width, float height, F2Vector axis, FInterval interval) {
		
		
		float xRight = xLeft + width;
		float yRight = yLeft + height;
		
		// bottom left corner
		float b1 = axis.dotProduct(xLeft, yLeft);
		
		// bottom right corner
		float b2 = axis.dotProduct(xRight, yLeft);
		
		interval.setBounds(b1, b2);
		
		// upper right corner
		interval.updateToFit(axis.dotProduct(xRight, yRight));
		
		//upper left corner
		interval.updateToFit(axis.dotProduct(xLeft, yRight));
	}
}
